package Demo06;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
    }
}

class Solution {
    public static void main(String[] args) {
        System.out.println(minDistance("ab", "ac"));
    }
    public static int minDistance(String word1, String word2) {
        return f1(word1, word2, 1, 1, 20);
    }

    /**
     * @param s1
     * @param s2
     * @param a  插入
     * @param b  删除
     * @param c  替换
     * @return
     */
    private static int f1(String s1, String s2, int a, int b, int c) {
        //n行 i
        //m列 j
        //s1的前i个变成s2的前j个
        int n = s1.length();
        int m = s2.length();

        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= m; i++) {
            //s1的前0个变成s2的前i个
            dp[0][i] = i * a;
        }
        for (int i = 1; i <= n; i++) {
            dp[i][0] = i * b;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if(s1.charAt(i-1)==s2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1];
                }else {
                    dp[i][j] = Math.min(dp[i-1][j-1]+c, Math.min(dp[i-1][j]+b, dp[i][j-1]+a));
                }
            }
        }
        return dp[n][m];
    }

}